package com.aqie.easy.tree;

import com.aqie.easy.structure.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 404 所有左叶子之和, 不是所有左子树之和
 * [1,2,3,4,5]
 */
public class SumOfLeftLeaves {
    int ans = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode node){
        if (node == null ) return;
        if (node.left != null && node.left.left==null && node.left.right==null) ans += node.left.val;
        dfs(node.left);
        dfs(node.right);
    }

    public int sumOfLeftLeaves2(TreeNode root) {
        int sum = 0;
        if(root==null||root.left==null&&root.right==null){
            return 0;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            TreeNode temp = que.poll();
            if(temp.left!=null){
                if(temp.left.left==null&&temp.left.right==null){
                    sum += temp.left.val;
                }
                que.offer(temp.left);
            }
            if(temp.right!=null){
                que.offer(temp.right);
            }
        }
        return sum;
    }
}
